/*
 * Copyright 2013 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.aplink.generic.google.maps;

import java.util.List;

import com.google.android.gms.maps.model.LatLng;

public class SphericalUtil {

	/**
	 * Returns the angle between two LatLngs, in radians. This is the same as
	 * the distance on the unit sphere.
	 */
	static double computeAngleBetween(final LatLng from, final LatLng to) {
		return SphericalUtil.distanceRadians(Math.toRadians(from.latitude),
				Math.toRadians(from.longitude), Math.toRadians(to.latitude),
				Math.toRadians(to.longitude));
	}

	/**
	 * Returns the area of a closed path on Earth.
	 *
	 * @param path
	 *            A closed path.
	 * @return The path's area in square meters.
	 */
	public static double computeArea(final List<LatLng> path) {
		return Math.abs(SphericalUtil.computeSignedArea(path));
	}

	/**
	 * Returns the distance between two LatLngs, in meters.
	 */
	public static double computeDistanceBetween(final LatLng from,
			final LatLng to) {
		return SphericalUtil.computeAngleBetween(from, to)
				* MathUtil.EARTH_RADIUS;
	}

	/**
	 * Returns the heading from one LatLng to another LatLng. Headings are
	 * expressed in degrees clockwise from North within the range [-180,180).
	 *
	 * @return The heading in degrees clockwise from north.
	 */
	public static double computeHeading(final LatLng from, final LatLng to) {
		// http://williams.best.vwh.net/avform.htm#Crs
		final double fromLat = Math.toRadians(from.latitude);
		final double fromLng = Math.toRadians(from.longitude);
		final double toLat = Math.toRadians(to.latitude);
		final double toLng = Math.toRadians(to.longitude);
		final double dLng = toLng - fromLng;
		final double heading = Math
				.atan2(Math.sin(dLng) * Math.cos(toLat),
						(Math.cos(fromLat) * Math.sin(toLat))
						- (Math.sin(fromLat) * Math.cos(toLat) * Math
								.cos(dLng)));
		return SphericalUtil.wrap(Math.toDegrees(heading), -180, 180);
	}

	/**
	 * Returns the length of the given path, in meters, on Earth.
	 */
	public static double computeLength(final List<LatLng> path) {
		if (path.size() < 2) {
			return 0;
		}
		double length = 0;
		final LatLng prev = path.get(0);
		double prevLat = Math.toRadians(prev.latitude);
		double prevLng = Math.toRadians(prev.longitude);
		for (final LatLng point : path) {
			final double lat = Math.toRadians(point.latitude);
			final double lng = Math.toRadians(point.longitude);
			length += SphericalUtil.distanceRadians(prevLat, prevLng, lat, lng);
			prevLat = lat;
			prevLng = lng;
		}
		return length * MathUtil.EARTH_RADIUS;
	}

	/**
	 * Returns the LatLng resulting from moving a distance from an origin in the
	 * specified heading (expressed in degrees clockwise from north).
	 *
	 * @param from
	 *            The LatLng from which to start.
	 * @param distance
	 *            The distance to travel.
	 * @param heading
	 *            The heading in degrees clockwise from north.
	 */
	public static LatLng computeOffset(final LatLng from, double distance,
			double heading) {
		distance /= MathUtil.EARTH_RADIUS;
		heading = Math.toRadians(heading);
		// http://williams.best.vwh.net/avform.htm#LL
		final double fromLat = Math.toRadians(from.latitude);
		final double fromLng = Math.toRadians(from.longitude);
		final double cosDistance = Math.cos(distance);
		final double sinDistance = Math.sin(distance);
		final double sinFromLat = Math.sin(fromLat);
		final double cosFromLat = Math.cos(fromLat);
		final double sinLat = (cosDistance * sinFromLat)
				+ (sinDistance * cosFromLat * Math.cos(heading));
		final double dLng = Math.atan2(
				sinDistance * cosFromLat * Math.sin(heading), cosDistance
				- (sinFromLat * sinLat));
		return new LatLng(Math.toDegrees(Math.asin(sinLat)),
				Math.toDegrees(fromLng + dLng));
	}

	/**
	 * Returns the location of origin when provided with a LatLng destination,
	 * meters travelled and original heading. Headings are expressed in degrees
	 * clockwise from North. This function returns null when no solution is
	 * available.
	 *
	 * @param to
	 *            The destination LatLng.
	 * @param distance
	 *            The distance travelled, in meters.
	 * @param heading
	 *            The heading in degrees clockwise from north.
	 */
	public static LatLng computeOffsetOrigin(final LatLng to, double distance,
			double heading) {
		heading = Math.toRadians(heading);
		distance /= MathUtil.EARTH_RADIUS;
		// http://lists.maptools.org/pipermail/proj/2008-October/003939.html
		final double n1 = Math.cos(distance);
		final double n2 = Math.sin(distance) * Math.cos(heading);
		final double n3 = Math.sin(distance) * Math.sin(heading);
		final double n4 = Math.sin(Math.toRadians(to.latitude));
		// There are two solutions for b. b = n2 * n4 +/- sqrt(), one solution
		// results
		// in the latitude outside the [-90, 90] range. We first try one
		// solution and
		// back off to the other if we are outside that range.
		final double n12 = n1 * n1;
		final double discriminant = ((n2 * n2 * n12) + (n12 * n12))
				- (n12 * n4 * n4);
		if (discriminant < 0) {
			// No real solution which would make sense in LatLng-space.
			return null;
		}
		double b = (n2 * n4) + Math.sqrt(discriminant);
		b /= (n1 * n1) + (n2 * n2);
		final double a = (n4 - (n2 * b)) / n1;
		double fromLatRadians = Math.atan2(a, b);
		if ((fromLatRadians < (-Math.PI / 2))
				|| (fromLatRadians > (Math.PI / 2))) {
			b = (n2 * n4) - Math.sqrt(discriminant);
			b /= (n1 * n1) + (n2 * n2);
			fromLatRadians = Math.atan2(a, b);
		}
		if ((fromLatRadians < (-Math.PI / 2))
				|| (fromLatRadians > (Math.PI / 2))) {
			// No solution which would make sense in LatLng-space.
			return null;
		}
		final double fromLngRadians = Math.toRadians(to.longitude)
				- Math.atan2(
						n3,
						(n1 * Math.cos(fromLatRadians))
						- (n2 * Math.sin(fromLatRadians)));
		return new LatLng(Math.toDegrees(fromLatRadians),
				Math.toDegrees(fromLngRadians));
	}

	/**
	 * Returns the signed area of a closed path on Earth. The sign of the area
	 * may be used to determine the orientation of the path. "inside" is the
	 * surface that does not contain the South Pole.
	 *
	 * @param path
	 *            A closed path.
	 * @return The loop's area in square meters.
	 */
	public static double computeSignedArea(final List<LatLng> path) {
		return SphericalUtil.computeSignedArea(path, MathUtil.EARTH_RADIUS);
	}

	/**
	 * Returns the signed area of a closed path on a sphere of given radius. The
	 * computed area uses the same units as the radius squared. Used by
	 * SphericalUtilTest.
	 */
	static double computeSignedArea(final List<LatLng> path, final double radius) {
		final int size = path.size();
		if (size < 3) {
			return 0;
		}
		double total = 0;
		final LatLng prev = path.get(size - 1);
		double prevTanLat = Math.tan(((Math.PI / 2) - Math
				.toRadians(prev.latitude)) / 2);
		double prevLng = Math.toRadians(prev.longitude);
		// For each edge, accumulate the signed area of the triangle formed by
		// the North Pole
		// and that edge ("polar triangle").
		for (final LatLng point : path) {
			final double tanLat = Math.tan(((Math.PI / 2) - Math
					.toRadians(point.latitude)) / 2);
			final double lng = Math.toRadians(point.longitude);
			total += SphericalUtil.polarTriangleArea(tanLat, lng, prevTanLat,
					prevLng);
			prevTanLat = tanLat;
			prevLng = lng;
		}
		return total * (radius * radius);
	}

	/**
	 * Returns distance on the unit sphere; the arguments are in radians.
	 */
	private static double distanceRadians(final double lat1, final double lng1,
			final double lat2, final double lng2) {
		return MathUtil.arcHav(MathUtil.havDistance(lat1, lat2, lng1 - lng2));
	}

	/**
	 * Returns the LatLng which lies the given fraction of the way between the
	 * origin LatLng and the destination LatLng.
	 *
	 * @param from
	 *            The LatLng from which to start.
	 * @param to
	 *            The LatLng toward which to travel.
	 * @param fraction
	 *            A fraction of the distance to travel.
	 * @return The interpolated LatLng.
	 */
	public static LatLng interpolate(final LatLng from, final LatLng to,
			final double fraction) {
		// http://en.wikipedia.org/wiki/Slerp
		final double fromLat = Math.toRadians(from.latitude);
		final double fromLng = Math.toRadians(from.longitude);
		final double toLat = Math.toRadians(to.latitude);
		final double toLng = Math.toRadians(to.longitude);
		final double cosFromLat = Math.cos(fromLat);
		final double cosToLat = Math.cos(toLat);

		// Computes Spherical interpolation coefficients.
		final double angle = SphericalUtil.computeAngleBetween(from, to);
		final double sinAngle = Math.sin(angle);
		if (sinAngle < 1E-6) {
			return from;
		}
		final double a = Math.sin((1 - fraction) * angle) / sinAngle;
		final double b = Math.sin(fraction * angle) / sinAngle;

		// Converts from polar to vector and interpolate.
		final double x = (a * cosFromLat * Math.cos(fromLng))
				+ (b * cosToLat * Math.cos(toLng));
		final double y = (a * cosFromLat * Math.sin(fromLng))
				+ (b * cosToLat * Math.sin(toLng));
		final double z = (a * Math.sin(fromLat)) + (b * Math.sin(toLat));

		// Converts interpolated vector back to polar.
		final double lat = Math.atan2(z, Math.sqrt((x * x) + (y * y)));
		final double lng = Math.atan2(y, x);
		return new LatLng(Math.toDegrees(lat), Math.toDegrees(lng));
	}

	/**
	 * Returns the non-negative remainder of x / m.
	 *
	 * @param x
	 *            The operand.
	 * @param m
	 *            The modulus.
	 */
	static double mod(final double x, final double m) {
		return ((x % m) + m) % m;
	}

	/**
	 * Returns the signed area of a triangle which has North Pole as a vertex.
	 * Formula derived from
	 * "Area of a spherical triangle given two edges and the included angle" as
	 * per "Spherical Trigonometry" by Todhunter, page 71, section 103, point 2.
	 * See http://books.google.com/books?id=3uBHAAAAIAAJ&pg=PA71 The arguments
	 * named "tan" are tan((pi/2 - latitude)/2).
	 */
	private static double polarTriangleArea(final double tan1,
			final double lng1, final double tan2, final double lng2) {
		final double deltaLng = lng1 - lng2;
		final double t = tan1 * tan2;
		return 2 * Math.atan2(t * Math.sin(deltaLng),
				1 + (t * Math.cos(deltaLng)));
	}

	/**
	 * Wraps the given value into the inclusive-exclusive interval between min
	 * and max.
	 *
	 * @param n
	 *            The value to wrap.
	 * @param min
	 *            The minimum.
	 * @param max
	 *            The maximum.
	 */
	static double wrap(final double n, final double min, final double max) {
		return ((n >= min) && (n < max)) ? n : (SphericalUtil.mod(n - min, max
				- min) + min);
	}

	private SphericalUtil() {
	}
}
